A content addressable memory (“CAM”) is a memory that receives a search word and searches the memory's storage locations to determine whether any of the locations contains data matching the search word. In many senses, this CAM lookup function is the inverse of the traditional memory read function; data in the form of the search word is received, and the memory outputs an address where the data is found (instead of the traditional read function where an address is received by the memory and the memory outputs data found at the address). CAM architecture is typically such that each memory cell incorporates comparison circuitry, such that the search word can be simultaneously compared against contents of the entire memory. This is to say, a CAM is typically used to provide a very quick lookup function against generally large sets of data, with results obtainable faster than from software-based lookup. Some CAM designs also feature a mask function, where one or more bits of the search word are masked during the search.
One type of CAM of particular interest is a Ternary CAM, or “TCAM.” A TCAM typically permits stored data words to be individually masked on a sub-word basis, typically bit-by-bit. That is, in contradistinction with search word masking indicated above, a TCAM permits parts of individual stored data words to be masked during storage, e.g., on a memory row-by-row basis. This feature can be very useful in some applications; for example, for network routers, a TCAM can be used to lookup a port matching a range of IP addresses, where the range would be represented by masked data in an individual storage location, and the address of that individual storage location would be used to retrieve the port. Other applications naturally exist.
To provide this individual storage location masking capability, a TCAM has one or more memory cells that can store both a data bit value and a mask indication. The mask indication, if set, causes the cell's built-in comparison circuitry to indicate a match for the cell irrespective of the state of the corresponding search word bit. As a result, the comparison can be made to ignore a subset of one or more bits of a given stored data word during the comparison process and to return a match for the given stored data word if its constituent bits otherwise match the search word.
A typical TCAM cell 101 is indicated in FIG. 1. It should be assumed that this cell is but one cell in a wide row of cells, with a TCAM memory device having many such rows, forming an array. The heart of the TCAM cell is two separate SRAM storage cells 105 and 107 each of which is used to store opposing logic values representing a stored data bit. For example, if a binary “1” is to be stored in the TCAM cell as a data bit, SRAM storage cell 105 is caused to store a logic “1,” while SRAM storage cell 107 is caused to store a logic “0.” If the stored data bit is instead a binary “0,” a logic “0” is stored in SRAM cell 105, while a logic “1” is stored in SRAM cell 107.
A matchline 103 common to an entire row of TCAM cells including cell 101 runs laterally through cell 101. To write data to the SRAM cells, a wordline pair WLX and WLY is asserted and data to be written is applied to differential bitlines BLX/BLX_(numeral 109) and BLY/BLY_(numeral 111). Note that WLX and WLY may be a common physical wordline. To later provide a search function for the depicted cell, the matchline 103 is raised to a precharge voltage (e.g., Vdd). A specific bit of a search word is then presented to the cell (depending on position of the cell within a memory row) via signal lines CDX/CDY (117/119) to compare cell contents to the corresponding bit of the search word; a differential voltage signal is used to represent the particular bit of the search word (generally Vdd/ground or ground/V) on these signal lines, dependent on whether the specific search word bit is a binary ‘1’ or ‘0.’ Should the SRAM cell contents (i.e., signals “X” and “Y”) represent a mismatch with the corresponding signals (CDX/CDY), then this mismatch causes a respective pair of FETs to both conduct and thereby discharge the matchline 103. For a given row in the TCAM device, if no TCAM cell in the row discharges the matchline, then the matchline remains at its sense voltage and therefore represents a match. In the TCAM cell of FIG. 1, both SRAM storage cells 105 and 107 can also be written-to to both store a logic “0” to represent a mask indication, which produces a match result for the TCAM cell during comparison irrespective of the applied search word (i.e., by preventing any discharge of the matchline by the particular TCAM cell). The matchline 103, the various bitlines 109 and 111 and the wordlines 113 and 115 are also used to provide conventional memory device operations, including writes to the cell, data reads, and other operations as appropriate.
Present applications of both CAMs and TCAMs are limited due to large cell size and, consequently, large device size; CAMs and TCAMs also suffer from very high power consumption relative to conventional memory. For example, conventional CAM cell designs such as the one seen in FIG. 1 may have twenty or more transistors and occupy a space greater than 80F2 (i.e., 80 times minimum feature cell size in area). Each transistor (or other component) also generally consumes power during normal cell operations (e.g., read, write or other operations). As a result, large (capacity) CAMs and TCAMs can be expensive to operate, especially for applications where software presents a timewise-manageable alternative. That is to say, CAM and TCAM devices are typically of small capacity, are expensive, or are both small and expensive. Because typical TCAM cell designs incorporate a mask function at the subword level, TCAM devices are typically even more expensive and limited in application than typical CAM designs. Despite these limitations, CAMs and TCAMs are still frequently utilized in applications where fast lookup functions against large storage capacities are desired, especially for internet routers, video and audio applications, regression and curve analysis, and other specialized forms of computational analysis.
Were it not for the memory cell size and power consumption problems just mentioned, it is believed that CAMs and TCAMs would be much more widely used, that is, both inside and outside of those specific applications just mentioned.
A need therefore exists for a CAM architecture that is more compact and consumes less power. Ideally, the techniques associated with this architecture would be extensible to TCAM operation. It is believed that fulfillment of these needs will lead to lower cost, larger-capacity CAMs and TCAMs, and increased usage of these devices in digital designs, even beyond those fields mentioned above. The CAM embodiments disclosed herein address these needs and provide further, related advantages.